package com.demo.java.OD301_350.OD340;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【找城市|城市聚集度(B卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146156562
 */
public class OdMain {
    private static List<Integer> cityGroup;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取城市数量
        int n = scanner.nextInt();
        List<List<Integer>> connections = new ArrayList<>();

        // 读取每条连接关系
        for (int i = 0; i < n - 1; i++) {
            connections.add(Arrays.asList(scanner.nextInt(), scanner.nextInt()));
        }

        // 存储每个城市对应的最大城市集群数
        Map<Integer, Integer> map = new HashMap<>();

        // 遍历每个城市，查找其最小的切割城市集群数
        for (int i = 0; i < n; i++) {
            final int index = i;
            List<List<Integer>> temp = new ArrayList<>(connections);
            // 移除与当前城市相连的城市
            temp.removeIf(connection -> connection.contains(index + 1));

            // 初始化城市组集合
            cityGroup = new ArrayList<>();
            // 如果没有连接，城市本身就是一个城市集群
            if (temp.isEmpty()) {
                cityGroup.add(1);
            } else {
                // 查找该城市能加入的集群
                findCityGroup(temp, new ArrayList<>());
            }

            // 排序并将结果存储到map中
            Collections.sort(cityGroup);
            map.put(i + 1, cityGroup.get(cityGroup.size() - 1));
        }

        // 查找最小的切割点并输出结果
        int min = Integer.MAX_VALUE;
        StringBuilder res = new StringBuilder();

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() < min) {
                min = entry.getValue();
                res = new StringBuilder(String.valueOf(entry.getKey()));
            } else if (entry.getValue() == min) {
                res.append(" ").append(entry.getKey());
            }
        }

        System.out.println(res);
    }

    /**
     * 查找城市所在的集群
     *
     * @param connections 当前的城市连接关系
     * @param cityList    当前城市所属的城市列表
     */
    public static void findCityGroup(List<List<Integer>> connections, List<Integer> cityList) {
        for (int i = 0; i < connections.size(); i++) {
            List<Integer> connection = connections.get(i);
            int a = connection.get(0);
            int b = connection.get(1);

            // 如果当前城市列表为空，加入连接的城市
            if (cityList.isEmpty()) {
                cityList.addAll(connection);
                connections.remove(i);

                // 如果没有连接了，则添加当前城市集群的大小
                if (connections.isEmpty()) {
                    cityGroup.add(cityList.size());
                }

                findCityGroup(connections, cityList);
            } else if (cityList.contains(a) || cityList.contains(b)) {
                // 如果该城市已存在于当前城市列表，合并城市
                cityList.removeAll(connection);
                cityList.addAll(connection);
                connections.remove(i);

                if (connections.isEmpty()) {
                    cityGroup.add(cityList.size());
                }

                findCityGroup(connections, cityList);
            } else if (i == connections.size() - 1) {
                // 如果遍历完成所有连接，添加当前城市集群
                cityGroup.add(cityList.size());
                findCityGroup(connections, new ArrayList<>());
            }
        }
    }
}